home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part2 / 13029 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  1.2 KB
  1. Path: gemini.coi.pw.edu.pl!news-adm@io.coi.pw.edu.pl
  2. From: "Marek Brudka (A. Pacut)" <brudka@ia.pw.edu.pl>
  3. Newsgroups: comp.lang.c
  4. Subject: Re: fast find algorithm
  5. Date: Wed, 03 Apr 1996 20:54:02 +0200
  6. Organization: Warsaw University of Technology
  7. Message-ID: <3162C94A.735F@ia.pw.edu.pl>
  8. References: <Dp8wE6.8DG@cix.compulink.co.uk>
  9. NNTP-Posting-Host: bobas.ia.pw.edu.pl
  10. Mime-Version: 1.0
  11. Content-Type: text/plain; charset=iso-8859-2
  12. Content-Transfer-Encoding: 7bit
  13. X-Mailer: Mozilla 3.0b2 (X11; I; SunOS 5.4 sun4c)
  14.  
  15. Stephen Etheridge wrote:
  16. > Does anyone have an search algoritm faster than a binary chop for the
  17. > following:
  18. > find a date from a sorted array of 1500 possible storage locations
  19. If you do not know anything about the statistical distribution of keys,
  20. you cannot improve the binary chop (assuming the same the distribution
  21. is uniform). But if the distribution is known, you can utilize this
  22. knowledge and statistically reduce the number of comparisions. I am not
  23. sure if this implies the speeding up of the searching, because there is
  24. a lot of additional work to do. Generally, for 1500 keys the ratio
  25. programming/(the speed of the searching) seems to be the best for
  26. bisectioning. 
  27.                         Regards
  28.                         Marek Brudka
  29.